
Patterns, Evaluation, Datatypes

* Types

 - name
 - values
 - operations

  Bool 
   - "bool" 
   - true, false
   - && || if then else

  Int
  - "int"
  - 0, 1, -1, 2, -2, ...
  - + -

  Pair
  - 'a "*" 'b
  - (val1, val2)
  - fst, snd

  Note: types can take arguments! (Type constructors)

  N-Tuple
  - 'a1 "*" ... "*" 'aN
  - (val1, ..., valN)
  - ?

  Lists
  - 'a "list"
  - [], [val], [v1, ..., vN]
  - @ :: 

  Functions
  - 'a "->" 'b
  - function x -> e
  - apply 

  let f x = e short for let f = (function x -> e)

* Patterns
 
Patterns discriminate the values of a given type

  match e:bool with
   | true -> e1
   | false -> e2 

  match e:int with
   | 0 -> e1
   | 1 -> e2
   | ...
   | n -> eN
   | _ -> eN

  match e:int*int with
    (x1, x2) -> e'(x1, x2)

  Note: Patterns Bind Variables!

  match e:int*...*int with
    (x1, x2, ..., xN) -> e'

  match e:int*(int*int) with
    (x1, (x2, x3)) -> e'

  match e:int list with
   | []      -> e1
   | x :: xs -> e2 

  match e:(int*int)list with
   | []             -> e1
   | (x1, x2) :: xs -> e2 

  match f with
    ??

pat ::= x | c(pat_) | _

(function pat1(v1_) -> e1(v1)
          pat2(v2_) -> e2(v2)
          ...
          patN(vN_) -> eN(vN)

(function true  -> e1
        | false -> e2) e

function x -> e === fun x -> e

** Exhaustive patterns

** Redundant patterns

* Expressions

e ::= x | c(e1,...,eN) | function pat -> e ... | e1 e2 | builtins(+, mod, *) |

let pat = e in e' === (function pat -> e') e

* Evaluation

e1 --> v1   e2 --> v2   v = v1 + v2
------------------------------------
          e1 + e2 --> v


 e1 --> v1   e2 --> v2
-----------------------
 (e1, e2) --> (v1, v2)


 e1 --> function ... | pat(x_) -> e(x) | ...    e2 --> v2  pat ~~ v2  [v_/x_] e --> v
--------------------------------------------------------------------------------------
                                e1 e2 --> v


call-by-value

if e then e1 else e2 ===

(function true -> e1
        | false -> e2) e

if 1 < 2 then 1 + 2 else ack 100 


e ---> \f. e''   [letrec e/f] e'' --> e'
-------------------------------------------
           letrec e --> e'



let rec f = 
  (print_string "hello\n";
   fun x -> x + x) in
 0

letrec : (t1 -> t2) -> (t1 -> t2)

fact = letrec (\f. function 0 -> 1 | n -> n * f(n-1))


let f = letrec 
  (print_string "hello\n";
   fun x -> x + x) in
 0

let x = e in e' 

(function x -> e') e

(letrec
  (print_string "hello\n";
   fun x -> x + x)) 0



let f = 
  letrec ((print_string "hello\n";
           fun x -> x + x)
in
  f 5

(letrec (print_string "hello\n"; fun f -> (function 0 -> 1 | n -> n * f (n-1)))) 5
--> "hello"
(letrec (fun f -> (function 0 -> 1 | n -> n * f (n-1)))) 5
-->
(letrec (fun f -> (function 0 -> 1 | n -> n * f (n-1)))) 5
-->
(function 0 -> 1 | n -> n * 
                   (letrec (fun f -> (function 0 -> 1 | n -> n * f (n-1)))) (n-1))  5
-->
5 * (letrec (fun f -> (function 0 -> 1 | n -> n * f (n-1)))) 4
-->    
5 * (letrec (fun f -> (function 0 -> 1 | n -> n * f (n-1)))) 4

(fun x -> x + x)



letrec e 

let fact = letrec (fun f -> (function 0 -> 1 | n -> n * f (n-1)))

fact --> (function 0 -> 1 | n -> n * fact (n-1))) 

* Datatypes

** Datatype declarations

Example: Lists.  RECURSIVE TYPE.

'datatype' introduces a NEW type, distinct from all other types.
ML type system is extended by the programmer.

A datatype declaration introduces

 - One or more type constructors
 - One or more value constructors

Type constructor
 - 0 or more arguments
 - 0 argument is a type
 
Value constructor
 - 0 or more args
 - 0 argumetn is a constant 

** Nonrecursive Datatypes 

*** Suits

datatype suit = Spades | Hearts | Diamonds | Clubs
datatype suit = Hearts | Spades | Clubs | Diamonds

order doesn't matter 

function
| outranks (Spades, Spades) = false
| outranks (Spades, ) = true
| outranks (Hearts, Spades) = false
| outranks (Hearts, Hearts) = false
| outranks (Hearts, ) = true
| outranks (Diamonds, Clubs) = true
| outranks (Diamonds, ) = false
| outranks (Clubs, ) = false

*** Option

Datatypes may be PARAMETERIZED

datatype 'a option = None | Some of 'a

Values of type string option: None, Some "sean"

fun reciprocal 0 = NONE
  | reciprocal n = SOME (1 div n)

case (reciprocal exp) of
  NONE => exp1
| SOME r => exp2

** Recursive Datatypes

datatype 'a tree =
  Empty 
| Node of 'a tree * 'a * 'a tree


1) Empty is a treee
2) if a and b are trees, then Node a b is a tree
3) Nothing else is a tree

**** Height function


**** Size function

datatype 'a tree =
    Empty 
  | Node of 'a * 'a tree list

datatype 'a tree =
  Empty |
  Node of 'a * 'a forest
and 'a forest =
  None |
  Tree of 'a tree * 'a forest

fun size tree Empty = 0
| size tree (Node ( , f)) = 1 + size forest f
and size forest None = 0
| size forest (Tree (t, f')) = size tree t + size forest f'

datatype 'a tree =
Empty |
Node of 'a branch * 'a branch
and 'a branch =
Branch of 'a * 'a tree

fun collect Empty = nil
| collect (Node (Branch (ld, lt), Branch (rd, rt))) =
ld :: rd :: (collect lt) @ (collect rt)

datatype expr =
  Numeral of int |
  Plus of expr * expr |
  Times of expr * expr

fun eval (Numeral n) = Numeral n
| eval (Plus (e1, e2)) =
let
val Numeral n1 = eval e1
val Numeral n2 = eval e2
in
Numeral (n1+n2)
end
| eval (Times (e1, e2)) =
let
val Numeral n1 = eval e1
val Numeral n2 = eval e2
in
Numeral (n1*n2)
end
